Computer data storage devices, such as disk drives and Redundant Array of Independent Disks (RAID), typically use a cache memory in combination with mass storage media (e.g., magnetic tape or disk) to save and retrieve data in response to requests from a host device. Cache memory, often referred to simply as “cache”, offers improved performance over implementations without cache. Cache typically includes one or more integrated circuit memory device(s), which provide a very high data rate in comparison to the data rate of non-cache mass storage medium. Due to unit cost and space considerations, cache memory is usually limited to a relatively small fraction of (e.g., 256 kilobytes in a single disk drive) mass storage medium capacity (e.g., 256 Gigabytes). As a result, the limited cache memory should be used as efficiently and effectively as possible.
Cache is typically used to temporarily store data that is the most likely to be requested by a host computer. By read pre-fetching (i.e., retrieving data from the host computer's mass storage media ahead of time) data before the data is requested, data rate may be improved. Data in cache is typically processed on a page basis. Typical storage devices use a fixed cache page size, and the size is typically implementation dependent.
Generally, storage device performance improves as read cache hit rate goes up. Read cache hit rate is a measure of frequency of accessing the read cache rather than the mass media (e.g., a disk). As is generally understood, the mass media typically takes much longer to access than the read cache. Thus, by increasing the read cache hit rate, data input/output (I/O) rate to the host can be increased. In order to take advantage of the relatively faster read cache, typical storage devices attempt to predict what data a host device will request in the near future and have that data available in the cache when the host actually requests it.
In a typical storage device, pre-fetching data involves reading a fixed amount of data from the mass storage media before the data is requested from the host. By way of example, a pre-fetch operation often occurs during a sequential workload. A sequential workload is generally a host workload that includes request(s) for data at logical addresses that are substantially sequential. After detecting a sequential workload, the storage device can pre-fetch data in the detected sequence and store that data in the read cache. If the host continues to request data in the detected sequence, the request data may be available in the read cache, thereby causing a read cache hit.
One problem that may occur is related to read cache capacity. Read cache is necessarily limited. As a result, a typical storage device reuses memory in the read cache repeatedly for pre-fetching operations. A typical storage device selects which data in the read cache to overwrite using a replacement algorithm, such as a least recently used (LRU) algorithm. Unfortunately, situations can arise in which data that is pre-fetched and stored in the read cache overwrites data in the read cache that the host will request. In other words, data that the host will request may reside in the read cache, available to satisfy the request, but because of the limited size of the read cache, that data is overwritten before the host requests the data. The likelihood of this problem occurring typically depends on the size of the read cache, and the amount of data that is pre-fetched. This particular problem can drastically reduce performance because when it occurs, the mass storage components are typically being worked considerably to accommodate pre-fetch operations, and yet the read cache hit rate is not improving or perhaps decreasing.
Another problem that may arise relates to response time of the mass storage components. A particular host workload may request data from the storage device faster than the read cache data can be replenished because of slow response times of the mass storage components. For instance, in a RAID system, the latencies associated with repositioning a disk drive actuator assembly and fetch data from the disk drive may be so slow relative to the rate of incoming host requests, that the data being fetched arrives in the read cache after a host request for the data. Latencies associated with mass storage components can vary depending on age, type, model, and workload. Typical storage device pre-fetch algorithms cannot effectively handle the various workloads and latencies that can arise. Thus, the read cache hit rate may be lower than expected under some situations.